package binaryTree;

import java.util.*;

/**
 * @program: data_structures_algorithms
 * @description: 广度，深度优先遍历，使用栈方式
 * @author: lld
 * @create: 2020-11-02 16:37
 **/
public class Demo2 {
    public static void main(String[] args) {
        //这里将线性的链表转化成非线性的二叉树，链表节点的顺序恰恰是二叉树前序遍历的顺 序。链表中的空值，代表二叉树节点的左孩子或右孩子为空的情况
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4, null, null}));
        TreeNode treeNode = createBinaryTree(inputList);
        pre(treeNode);
        in(treeNode);
        System.out.println("深度：" + depth(treeNode));
        levelOrder(treeNode);

    }

    /**
     * @Description: 构造树结构
     **/
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        TreeNode node = null;
        if (inputList == null || inputList.isEmpty()) {
            return null;

        }
        Integer data = inputList.removeFirst();
        if (data != null) {
            node = new TreeNode(data);
            node.left = createBinaryTree(inputList);
            node.right = createBinaryTree(inputList);
        }
        return node;

    }

    /**
     * @Description: 树的广度优先遍历（层次遍历）
     **/
    private static void levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);//首先添加根节点
        while (!queue.isEmpty()) {
            TreeNode treeNode = queue.poll();
            System.out.printf("%d\t", treeNode.data);
            if (treeNode.left != null)
                queue.offer(treeNode.left);
            if (treeNode.right != null)
                queue.offer(treeNode.right);
        }

    }

    /**
     * @Description: 前序遍历
     **/
    private static void pre(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = root;
        //单treeNode=null时，stack不为空将继续
        while (treeNode != null || !stack.isEmpty()) {
            //迭代访问节点的左孩子，并入栈
            if (treeNode != null) {
                System.out.printf("%d\t", treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            //如果节点无左子树,弹出栈顶元素，访问右子树
            else {
                treeNode = stack.pop();
                treeNode = treeNode.right;
            }
        }
    }

    /**
     * @Description: 中序遍历
     **/
    private static void in(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = root;
        //单treeNode=null时，stack不为空将继续
        while (treeNode != null || !stack.isEmpty()) {
            //迭代访问节点的左孩子，并入栈
            if(treeNode != null) {
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            //如果节点无左子树,弹出栈顶元素，访问右子树
            else {
                treeNode = stack.pop();
                System.out.printf("%d\t", treeNode.data);
                treeNode = treeNode.right;
            }
        }
    }

    /**
     * @Description: 二叉树的深度
     **/
    private static int depth(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int l = depth(treeNode.left);//左子树深度
        int r = depth(treeNode.right);//右子树深度
        return Math.max(l, r) + 1;
    }
}

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int data) {
        this.data = data;
    }
}
